﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MultiResolutioning.Structures;

namespace MultiResolutioning.Collections
{
	/// <summary>
	/// Klasa daje mozliwosc stworzenia posortowanej listy wierzcholkow z istniejacej listy.
	/// </summary>
	public class SortedVertexList
	{
		private IList<Vertex> list;

		public SortedVertexList(IList<Vertex> list)
		{
			this.list = list;
		}

		/// <summary>
		/// Wstawianie binarne.
		/// </summary>
		/// <param name="item">Element.</param>
		public void BinaryInsert(Vertex item)
		{
			int imin = 0;
			int imax = this.list.Count - 1;
			int imid = 0;

			Vertex temp;
			while (imax > imin)
			{
				imid = (imax - imin >> 1) + imin;
				temp = this.list[imid];

				if (temp.vertexId < item.vertexId)
				{
					imin = imid + 1;
				}
				else if (temp.vertexId > item.vertexId)
				{
					imax = imid - 1;
				}
				else
				{
					this.list.Insert(imid + 1, item);
					return;
				}
			}

			if (this.list[imin].vertexId < item.vertexId)
			{
				this.list.Insert(imin + 1, item);
			}
			else
			{
				this.list.Insert(imin, item);
			}
		}

		/// <summary>
		/// Wyszykiwanie binarne.
		/// </summary>
		/// <param name="vertexId">Indeks wierzcholka.</param>
		public Vertex FindBinary(int vertexId)
		{
			int imin = 0;
			int imax = this.list.Count - 1;
			int imid = 0;

			Vertex temp;
			while (imax > imin)
			{
				imid = (imax - imin >> 1) + imin;
				temp = this.list[imid];

				if (temp.vertexId < vertexId)
				{
					imin = imid + 1;
				}
				else if (temp.vertexId > vertexId)
				{
					imax = imid - 1;
				}
				else
				{
					temp.InCollectionIndex = imid;
					return temp;
				}
			}

			this.list[imin].InCollectionIndex = imin;
			return this.list[imin];
		}

		/// <summary>
		/// Reorganiuzuje element
		/// </summary>
		/// <param name="itemIndex">Indeks elementu.</param>
		public void UpdateAt(int itemIndex)
		{
			Vertex temp = this.list[itemIndex];

			if (itemIndex == 0)
			{
				BubbleUp(itemIndex);
			}
			else if (itemIndex == this.list.Count - 1)
			{
				BubbleDown(itemIndex);
			}
			else
			{
				if (temp.vertexId > this.list[itemIndex + 1].vertexId)
					BubbleUp(itemIndex);
				else
					BubbleDown(itemIndex);
			}
		}

		private void BubbleUp(int itemIndex)
		{
			while (itemIndex < this.list.Count - 1 && this.list[itemIndex].vertexId > this.list[itemIndex + 1].vertexId)
			{
				Swap(itemIndex, itemIndex + 1);
				itemIndex++;
			}
		}
		
		private void BubbleDown(int itemIndex)
		{
			while (itemIndex > 0 && this.list[itemIndex].vertexId < this.list[itemIndex - 1].vertexId)
			{
				Swap(itemIndex, itemIndex - 1);
				itemIndex--;
			}
		}
		
		private void Swap(int index1, int index2)
		{
			Vertex temp = this.list[index2];
			this.list[index2] = this.list[index1];
			this.list[index1] = temp;
		}
	}
}
